//
// Created by ASUS on 2023/10/12.
//
#include <bits/stdc++.h>

using namespace std;

vector<int> getNext(string &s){
	int n=s.length();
	vector<int> Next(n,0);
	for(int i=1;i<n;i++){
		int j=Next[i-1];
		while (j&&s[j]!=s[i]) j=Next[j-1];
		Next[i]=(s[i]==s[j])?j+1:0;
	}
	return Next;
}

vector<int> kmp(string &s,string &p){
	vector<int> res;
	int n=s.length(),m=p.length();
	auto Next=getNext(p);
	int j=0,cnt=0,first=-1,last=-1;
	for(int i=0;i<n;i++){
		while (j&&s[i]!=p[j]) j=Next[j-1];
		if(s[i]==p[j]) j++;
		if(j==m){
			if(first==-1)first=i-m+1;
			last=i-m+1;
			res.push_back(i-m+1);
			cnt++;
			j=Next[j-1];
		}
	}
	return {cnt,first,last};
	//return res;
}

int main(){

	string a="abacabab";
	string b="abacabab";
	cout<<a.length()<<"\n";
	vector<int> f=kmp(a,b);
//	clock_t start=clock();
//	long long v=0;
//	for(int i=1;i<5e8;i++){
//		v+=i;
//	}
//	clock_t end=clock();
//	double elapsed_time = (double)(end - start) / CLOCKS_PER_SEC;
//	printf("Elapsed time: %f seconds\n", elapsed_time);

	return 0;
}

